package bucketsort;

import org.junit.jupiter.api.Test;

import java.text.NumberFormat;
import java.util.Arrays;
import java.util.Random;
import java.util.stream.IntStream;

/**
 * 计数排序
 */
public class CountSort {

    NumberFormat num = NumberFormat.getInstance();

    static int count = 0;

    @Test
    public void client() {
        Random random = new Random(1);
        for (int i = 0; i < 500000; i++) {
            /**
             * 随机样本长度
             */
            int anInt = random.nextInt(100) + 1;
            int[] arr = new int[anInt];
            for (int j = 0; j < anInt; j++) {
                /**
                 * 随机样本数据
                 */
                arr[j] = random.nextInt(100);
            }
            System.out.println("=======================第" + (i + 1) + "次=======================");
            System.out.println("排序前==》" + Arrays.toString(arr));
            countSort(arr);
            System.out.println("排序后==》" + Arrays.toString(arr));
            int[] newArr = Arrays.copyOf(arr, arr.length);
            boolean logarithmizer = logarithmizer(arr, newArr);
            if (logarithmizer) {
                System.out.println("对数器验证结果：PASS");
            } else {
                System.out.println("对数器验证结果：NOT PASS");
            }
        }

        System.out.println("==============================================");
        System.out.println("=======                                 ======");
        System.out.println("=======    验证不通过结果为：" + count + "   ======");
        System.out.println("=======                                 ======");
        System.out.println("==============================================");
    }

    /**
     * 定义一个长度为10的数组， 因为每个数据的个位、十位、百位……最大就是0~9是个数据。
     * @param arr 原始数据
     */
    private void countSort(int[] arr) {
        // 定义两个辅助数组
        String[] help = new String[arr.length];
        String[] help1 = new String[arr.length];
        // 获取数据中最大数据的位数
        int max = IntStream.of(arr).max().getAsInt();
        int maxLeg = String.valueOf(max).length();
        num.setMinimumIntegerDigits(maxLeg);
        // 原数组中其他数据不够最大数据的位数时，前边补充0补足位数。
        for (int i = 0; i < arr.length; i++) {
            help[i] = num.format(arr[i]);
        }

        int[] count;
        /**
         * 根据最大位数，对每一个数据进行分桶
         * 比如：第一次循环，个位为1的数据的个数记录到count中…………
         *      第二次循环，十位为1的数据数据的个数记录到count中…………
         *      …………
         *  最后将处理好的count进行累加,形成新的count，也就是当前位置上数值是前边一个位置上数据和当前位置上的数据的总和。
         */
        for (int i = maxLeg - 1; i > -1; i--) {
            count = new int[10];
            for (String s : help) {
                int index = Integer.parseInt(String.valueOf(s.charAt(i)));
                count[index]++;
            }

            // 将处理好的count进行累加.形成新的count
            for (int i1 = 1; i1 < count.length; i1++) {
                count[i1] = count[i1] + count[i1 - 1];
            }

            /**
             * 然后数据应该按照从右到左的顺序循环
             * 例如：最后一个位置上的数据A，个位数为2，那么找到count中下标为2的位置上的数据，假如为5，那么
             * A应该放在数组下标为4的位置上，并且count中下标为2的位置上的数据减一，就变成了4，下一个位置上的数据同理。
             */
            for (int i1 = help.length - 1; i1 >= 0; i1--) {
                int index = Integer.parseInt(String.valueOf(help[i1].charAt(i)));
                help1[--count[index]] = help[i1];
            }
            // 每次处理过一遍的数组参与下一次处理流程，最终数组有序
            help = Arrays.copyOf(help1, help1.length);
        }

        // 最后将完全处理好的数组，覆盖到最原始的数据中，做到原数组有序
        for (int i = 0; i < help1.length; i++) {
            arr[i] = Integer.parseInt(help1[i]);
        }
    }

    /**
     * 对数器验证：思想，用java提供的工具类和我们自己写的算法对处理后的数组，
     * 进行每一个元素比对。
     */
    private static boolean logarithmizer(int[] arr, int[] newArr) {
        /**
         * java提供的工具类
         */
        Arrays.sort(newArr);
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != newArr[i]) {
                count++;
                return false;
            }
        }

        return true;
    }
}
